package org.example.top40;

import java.util.Random;

public class main08 {
    static Random random = new Random();
    //排序数组 快排
    public static void main(String[] args) {

        int[] nums={5,1,1,2,0,0};
        int low = 0;
        int high = nums.length - 1;
        quickSorts(low,high,nums);
        for (int num:nums){
            System.out.println(num);
        }
    }

    private static void quickSorts(int low, int high, int[] nums) {
        if(low<high){
            int pi=partation(low,high,nums);
            quickSorts(low,pi-1,nums);
            quickSorts(pi+1,high,nums);
        }
    }

    private static int partation(int low, int high, int[] nums) {
        int indexRandom=random.nextInt(high-low+1)+low;
        swaps(indexRandom,low,nums);
        int piNum=nums[low];
        while(low<high){
            while(low<high&&nums[high]>=piNum){
                if(nums[high]==piNum){
                    high--;
                    break;
                }
                high--;
            }
            nums[low]=nums[high];
            while(low<high&&nums[low]<=piNum){
                if(nums[low]==piNum){
                    low++;
                    break;
                }
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low]=piNum;
        return low;
    }

    private static void swaps(int indexRandom, int low, int[] nums) {
        int t=nums[indexRandom];
        nums[indexRandom]=nums[low];
        nums[low]=t;
    }

}
